/**
 * 
 */
package logic;

import java.util.Vector;
import datamodel.rucksack.Rucksack;
import datamodel.rucksack.RucksackObject;
import datamodel.tree.Tree;
import datamodel.tree.TreeNode;
import datamodel.tree.TreeNodeFactory;
import datamodel.tree.linked.LinkedTree;
import datamodel.tree.sequential.SequentialTree;

/**
 * holds all necessary method to create trees, filter them and find optimal
 * rucksacks
 * 
 * @author Jakob Karolus, Kevin Munk
 * @version 1.0
 * 
 */
public class RucksackTreeBuilder {

	private Tree tree;
	// For finding the most valuable rucksack
	Rucksack mostValuableRucksack = new Rucksack(0); // capacity not relevant

	/**
	 * constructor
	 * 
	 * @param flag
	 *            true: uses SequentialTre; false: uses LinkedTree
	 */
	public RucksackTreeBuilder(boolean flag) {
		if (flag) {
			this.tree = new SequentialTree();
		} else {
			this.tree = new LinkedTree();
		}
	}

	/**
	 * creates a tree out of the given RucksackObjects using the following
	 * schematic:<br>
	 * Starting with the first RucksackObject the methods adds it only to the
	 * right node; then processes over the remaining objects
	 * 
	 * @param objects
	 *            the objects to put into the rucksack
	 * @param capacity
	 *            the capacity of the rucksack
	 */
	public void createRucksackTree(Vector<RucksackObject> objects, int capacity) {
		if(objects == null){
			objects = new Vector<RucksackObject>();
		}
		TreeNode root =  TreeNodeFactory.getNodeForTree(tree, new Rucksack(capacity));
		tree.clearTree();
		tree.setCurrentNode(root);
		recursivelyCreateRucksack(objects, capacity, 0);
	}
	
	
	private void recursivelyCreateRucksack(Vector<RucksackObject> objects, int capacity, int treeLevel) {
		TreeNode cn = tree.getCurrentNode();
		if(treeLevel== objects.size())
			return;
			
		// create left child
		TreeNode leftChild = TreeNodeFactory.getNodeForTree(tree, cn.getRucksack()); // left child has same rucksack as parent
		tree.setLeftNode(leftChild);
		
		RucksackObject rob = objects.get(treeLevel);
			
		if(capacityCondMet(capacity, rob)) {
			// create right child
			Rucksack rcR = new Rucksack(capacity);
			for(RucksackObject pRob : cn.getRucksack().getElements()) { // copy from parent
				rcR.insert(pRob);
			}
			rcR.insert(rob); // additional RucksackObject
			TreeNode rightChild = TreeNodeFactory.getNodeForTree(tree, rcR);
			tree.setRightNode(rightChild);			
		}
		// repeat for left node
		tree.moveToLeftNode();
		recursivelyCreateRucksack(objects, capacity, treeLevel+1);
		
		tree.moveToParentNode();
		
		if(!tree.hasRightNode())
			return;
		tree.moveToRightNode();
		
		recursivelyCreateRucksack(objects, capacity, treeLevel+1);
		
		tree.moveToParentNode();
	}
	

	// for linked trees
	private boolean capacityCondMet(int capacity, RucksackObject rob) {
		int weightOfCurrentNode = tree.getCurrentNode().getRucksack().getWeight();
		return (weightOfCurrentNode + rob.getWeight()) <= capacity;
		
	}
	

	/**
	 * creates a tree out of the given RucksackObjects using the following
	 * schematic:<br>
	 * Starting with the first RucksackObject the methods adds it only to the
	 * right node; then processes over the remaining objects.<br>
	 * The method findOptimalRucksack() on this tree always delivers a rucksack with the given
	 * neededObjects
	 * 
	 * @param objects
	 *            the objects to put into the rucksack
	 * @param neededObjects
	 *            the objects that MUST be in the rucksack at all costs
	 * @param capacity
	 *            the capacity of the rucksack
	 * @throws IllegalArgumentException
	 *             if the neededObjects don't fit into the rucksack
	 */
	public void createRucksackTree(Vector<RucksackObject> objects,
			Vector<RucksackObject> neededObjects, int capacity) {
		if(objects == null){
			objects = new Vector<RucksackObject>();
		}
		if(neededObjects == null){
			createRucksackTree(objects, capacity);
		}
		TreeNode root =  TreeNodeFactory.getNodeForTree(tree, new Rucksack(capacity));
		for(RucksackObject o : neededObjects){
			if(objects.contains(o)){
				objects.remove(o);
			}
			if(! root.getRucksack().insert(o)){
				throw new IllegalArgumentException();
			}
		}
		tree.clearTree();
		tree.setCurrentNode(root);
		recursivelyCreateRucksack(objects, capacity, 0);
	}

	/**
	 * goes recursively over all nodes of the tree and finds the best rucksack
	 * in the leafs.
	 * 
	 * @return the rucksack with the best value. The method returns null, if no
	 *         root exists
	 */
	public Rucksack findOptimalRucksack() {
		tree.moveToRoot();
		// sets the optimal rucksack
		findORHelper();
		return mostValuableRucksack;
	}

	private void findORHelper() {
		TreeNode cn = tree.getCurrentNode();
		Rucksack r = cn.getRucksack();
		if(r.getValue() > mostValuableRucksack.getValue())
			mostValuableRucksack = r;
		
		// don't go any further. leaf reached
		if(!tree.hasLeftNode() && !tree.hasRightNode())
			return;
		
		if(tree.hasLeftNode()) {
			tree.moveToLeftNode();
			findORHelper();
		}
		
		if(!tree.hasParentNode())
			return;
		tree.moveToParentNode();
		
		if(tree.hasRightNode()) {
			tree.moveToRightNode();
			findORHelper();
		}
		else
			return;
		if(!tree.hasParentNode())
			return;
		tree.moveToParentNode();
	}

	/**
	 * filters the given tree<br>
	 * each rucksack which doesn't fulfill the constraints not part of the list<br>
	 * 
	 * @param constraints
	 *            the constraints to use, if null the constraints are
	 *            irrelevant.
	 * @return a list containing the filtered rucksacks
	 */
	public Vector<Rucksack> filter(Constraints constraints) {
		// If the constraints are not defined, provide default constraints
		if(constraints == null){
			constraints = new Constraints(Integer.MIN_VALUE, Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MAX_VALUE);
		}
		// empty tree -> empty vector
		if(!tree.moveToRoot())
			return new Vector<Rucksack>(); // no root -> empty tree
		
		// we're at the root
		Vector<Rucksack> rucksacks = new Vector<Rucksack>();
		filterHelper(constraints, rucksacks); // use accumulator
		return rucksacks;	
	}

	private void filterHelper(Constraints constraints, Vector<Rucksack> rucksacks) {
		// don't go any further. leaf reached
		if(!tree.hasLeftNode() && !tree.hasRightNode())
			return;
		
		if(tree.hasLeftNode()) {
			tree.moveToLeftNode();
			// never inspect rucksacks of left nodes
			filterHelper(constraints, rucksacks);
		}
		
		if(!tree.hasParentNode()) {
			return;
		}
		tree.moveToParentNode();
		
		if(tree.hasRightNode()) {
			tree.moveToRightNode();
			// filter
			Rucksack r = tree.getCurrentNode().getRucksack();
			if(fulfillsConstraints(constraints, r)) {
				rucksacks.add(r);
			}
			filterHelper(constraints, rucksacks);
		}
		else
			return;
		
		if(!tree.hasParentNode())
			return;
		tree.moveToParentNode();
	}

	private boolean fulfillsConstraints(Constraints constraints, Rucksack r) {
		if(r == null){
			return false;
		}
		boolean minValue = r.getValue() >= constraints.getMinValue();
		boolean maxValue = r.getValue() <= constraints.getMaxValue();
		boolean minObjects = r.getSize() >= constraints.getMinObjects();
		boolean maxObjects = r.getSize() <= constraints.getMaxObjects();
		return minValue && maxValue && minObjects && maxObjects;
		
	}

	/**
	 * @return the current tree of this builder
	 */
	public Tree getTree() {
		return tree;
	}
}
